//https://leetcode.cn/problems/merge-two-sorted-lists/description/
//合并有序链表

struct ListNode {
    int val;
    struct ListNode *next;
};
typedef struct ListNode ListNode;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL)
    return list2;
    if(list2 == NULL)
    return list1;

    ListNode *l1 = list1, *l2 = list2;

    ListNode *newhead = NULL;
    ListNode *newtail = NULL;
    newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
    //创建没有意义的结点，以避免在插入第一个结点时发生错误
    //带头链表

    while(l1 && l2)
    {
        if(l1->val > l2->val)
        {
            newtail->next = l2;
            newtail = newtail->next;
            l2 = l2->next;
        }
        else
        {
            newtail->next = l1;
            newtail = newtail->next;
            l1 = l1->next;
        }
        
    }

    if(l1 == NULL)
    {
        newtail->next = l2;
    }
    else
    {
        newtail->next = l1;
    }

    ListNode* del = newhead;
    newhead = newhead->next;
    free(del);
    del = NULL;

    return newhead;
}